package com.ohc.leetcode.数组;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 2022年5月25日18:19:46
 * https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/
 */
public class 删除有序数组中的重复项26 {
    public static int removeDuplicates(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();  // 记录重复出现的数字

        int size = nums.length;
        int result = 0;
        for (int i = 0; i < size; i++) {
            if (!map.containsKey(nums[i])) {  // 如果不包含这个数字的话
                map.put(nums[i], 0);
            } else {   // 包含了的话就进行删除
                for (int j = i; j < size; j++) {
                    if (j != size - 1)
                        nums[j] = nums[j + 1];  // 进行覆盖删除
                }
                size--;
                i--;   // 回调
            }
        }

        return size;
    }

    /**
     * 双指针 参考写法
     *
     * @param nums
     * @return
     */
    public static int removeDuplicates2(int[] nums) {
//        int slow = 1;
//        int fast = 1;
//        while (fast < nums.length) {
//            if (nums[fast] != nums[fast - 1]) {
//                nums[slow] = nums[fast];
//                ++slow;
//            }
//                fast++;
//
//        }
//        return slow;
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int fast = 1, slow = 1;
        while (fast < n) {
            if (nums[fast] != nums[fast - 1]) {
                nums[slow] = nums[fast];
                ++slow;
            }
            ++fast;
        }
        return slow;

    }


    public static void main(String[] args) {
        int[] num = new int[]{1, 1, 2, 3, 3, 4, 5, 1, 3, 5};
        int len = removeDuplicates(num);
        for (int i = 0; i < len; i++) {
            System.out.println("num[i] = " + num[i]);
        }

    }
}
